Matching available network servers with clients needing the services provided by the servers is a classic problem encountered all the time in a client-server networking environment. Due to various limitations and restrictions, a client may be able to work only with some of the servers and/or within certain time windows. If the servers that can work with the client are already busy serving other clients, the client would have to wait in line for its turn to be served. Without an effective way to control the matching of the clients to the servers based on their matching constraints, some clients may be assigned to servers with long queue lines and have to wait for a long time to be served while other servers are sitting idle. This not only results in a significant waste of the server resources but also causes unacceptable delays experienced by the clients.
This client-server matching problem is not peculiar to the computer world. Rather, it is manifested in various forms in real life. For instance, this matching problem can be presented as a so-called “Swiss Bank Problem.” In this problem, there are a given number of bank tellers each speaking one of several different languages (e.g., German, Italian, French, Romansh, and English, etc.), and a plurality of customers waiting to be served. Each customer speaks one or more of the languages spoken by the respective tellers. As a result of the language constraints, each customer can only work with a subset of the available tellers. If the customers walking into the bank are arbitrarily put in lines in front of the tellers that speak their languages, the lines can be of significantly uneven lengths. As a result, some customers will have to wait in line for a long time while some tellers are not servicing any customer, and the total customer wait time is much higher than it should be.
Interestingly, even though the client-server matching problem is prevalent in networking applications, no simple and effective solutions to this problem have been proposed. For instance, there are certain “bipartite matching” algorithms that can be found in standard textbooks on algorithms. Those solutions, however, are too simple, as they can only handle the special case where each server can handle only one client. Thus, they are not useful for the much more common situations in which the number of the clients waiting to be served exceeds the number of the servers. In contrast, there are several algorithms of the minimum-cost maximum-flow type that may be used to solve the matching problem, but these solutions are too complicated because they try to handle additional characteristics of the problem, such as that some servers are faster than others or that some clients take more time to serve than others. Accordingly, they tend to be difficult to implement and slow in finding an optimal match. Thus, what is needed is an effective yet simple computer-executable method for finding an optimal matching between a plurality of clients and a smaller number of services, based on the matching constrains of the clients and servers. It will be appreciated that such a solution has wide applications in client-server networking applications.